package com.github.jcooky.structure;

public abstract class AbstractTree implements Tree {
	protected class TreeNode implements Node {
		Object e;
		Node parent;
		NodeList children = new LinkedList();

		public Object element() {
			return e;
		}

		public Node parent() {
			return parent;
		}

		public List children() {
			return children;
		}
	}

	protected Node root;
	protected int n;

	public Iterator iterator() {
		return elements().iterator();
	}

	public int size() {
		return n;
	}

	public boolean isEmpty() {
		return n == 0;
	}

	public List elements() {
		return null;
	}

	public List nodes() {
		return null;
	}

	public Node root() {
		return root;
	}

	public Node parent(Node v) {
		return v.parent();
	}

	public List children(Node v) {
		return v.children();
	}

	public boolean isInternal(Node v) {
		return !v.children().isEmpty();
	}

	public boolean isExternal(Node v) {
		return v.children().isEmpty();
	}

	public boolean isRoot(Node v) {
		return root.equals(v);
	}

	public Object replace(Node v, Object e) {
		Object o = ((TreeNode)v).e;
		((TreeNode)v).e = e;
		return o;
	}

	public void preOrder(Visitor visitor) {
		preOrder(root, visitor);
	}
	
	private void preOrder(Node v, Visitor visitor) {
		visitor.visit(v);
		
		NodeList children = ((TreeNode)v).children;
		for (NodeList.Node node = children.first(); node != children.last().getNext(); node = children.next(node)) {
			preOrder((Node)node.element(), visitor);
		}
	}

	public void postOrder(Visitor visitor) {
		postOrder(root, visitor);
	}

	private void postOrder(Node v, Visitor visitor) {
		visitor.visit(v);
		
		NodeList children = ((TreeNode)v).children;
		for (NodeList.Node node = children.last(); node != children.prev(children.first()); node = children.prev(node)) {
			postOrder((Node)node.element(), visitor);
		}
	}
}
